#ifndef naivebinarytree_h 
#define naivebinarytree_h 
/*
    Speedbump aka Project Kimbula
    Copyright (C) 2010  Ping Shin Ching

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see http://www.gnu.org/licenses.

	Ping Shin Ching
	righteous.ninja@gmail.com OR ping_sc@hotmail.com
	More information at http://www.tidytutorials.com/p/speedbump.html
 */

/* 
 * Really naive binary tree to support the cache
 */
typedef int(*nb_binarytredicate_fp)(void*, void*);
typedef void(*nb_deallocator_fp)(void*, void*);
typedef void (*nb_show_fp)(void*, void*);

typedef struct bnode_T bnode;
struct bnode_T{
	void* value;
	void* data;
	bnode *left, *right, * parent;
};
short tree_insert(bnode** node, void* value, void* data, nb_binarytredicate_fp compare);
short tree_insert_overwrite(bnode** node, void* value, void* data, nb_binarytredicate_fp compare, nb_deallocator_fp dealloc);
void* tree_search(bnode* node, void* value, nb_binarytredicate_fp compare);
short tree_delete(bnode **node, void* value, nb_binarytredicate_fp compare, nb_deallocator_fp dealloc);
void tree_destroy(bnode** node,  nb_binarytredicate_fp compare, nb_deallocator_fp dealloc);

short tree_insert_i2(bnode** node, void* value, void* data, nb_binarytredicate_fp compare, nb_deallocator_fp dealloc, short overwrite);
void* tree_search_i2(bnode* node, void* value, nb_binarytredicate_fp compare);

/* Insert without overriding */
short tree_insert( bnode** node, void* value, void* data, nb_binarytredicate_fp compare){
	return tree_insert_i2(node, value, data, compare, 0,0);
}

/* Insert with overriding */
short tree_insert_overwrite( bnode** node, void* value, void* data, nb_binarytredicate_fp compare, nb_deallocator_fp dealloc){
	return tree_insert_i2(node, value, data, compare, dealloc,1);
}

/* Insert with the option of overriding */
short tree_insert_i2( bnode** node, void* value, void* data, nb_binarytredicate_fp compare, nb_deallocator_fp dealloc, short overwrite){
	bnode *n, *t;
	int res;
	t=(bnode*)malloc(sizeof( bnode));
	t->value = value;
	t->data = data;
	t->left = 0;
	t->right = 0;
	t->parent = 0;;

	if(!*node){
		t->parent=0;
		*node=t;	
		return 1;
	}
	n = *node;
	while(n){
		t->parent=n;
		if((res=compare(value, n->value))==0){
			if(overwrite){
				dealloc(n->value, n->data);
				free(t);
				n->data = data;	
				n->value = value;
				return 0;
			}	
			else
				return 0;
		}
		else if(res > 0 ){
			if(!n->right){
				n->right=t;
				return 1;
			}
			n=n->right;
		}
		else{
			if(!n->left){
				n->left=t;	
				return 1;
			}
			n=n->left;
		}
	}
	return -1;
}

/* Search the tree for a value */
void* tree_search( bnode* node, void* value, nb_binarytredicate_fp compare){
	bnode* n;
	if((n=(bnode*)tree_search_i2(node, value, compare)))
		return n->data;
	else
		return 0;

}

/* Search the tree for a value */
void* tree_search_i2( bnode* node, void* value, nb_binarytredicate_fp compare){
	int res;
	while(node){
		if((res=compare(value, node->value))==0)
			 return node;
		if(res>0)
			node=node->right;
		else
			node=node->left;
	}
	return 0;
}

/* Delete a value  - replace with inorder successor*/
short tree_delete(bnode **node, void* value, nb_binarytredicate_fp compare, nb_deallocator_fp dealloc){
	bnode *n, *m;

	if((n=(bnode*)tree_search_i2(*node, value, compare))){
		m=n;
		if(n->right){
			n=n->right;
			while(n->left){
				n=n->left;
			}
		}
		if(n==m && m->parent==0){
				if(n->left){
					*node=n->left;
					n->left->parent=0;
				}
				else
					*node=0;
		}
		else{
			if(n->parent->left==n)
				n->parent->left=n->right?n->right:n->left;
			else
				n->parent->right=n->right?n->right:n->left;;

			if(n->left)
				n->left->parent=n->parent;
			if(n->right)
				n->right->parent=n->parent;
			if(n!=m){
				if(m->parent){
					if(m->parent->left==m)
						m->parent->left=n;
					else
						m->parent->right=n;
					n->parent=m->parent;
				}else{
					n->parent=0;
					*node=n;
				}
	
				n->left=m->left;
				if(n->left)
					n->left->parent=n;
				n->right=m->right;
				if(n->right)
					n->right->parent=n;
			}

		}
		dealloc(m->value, m->data);
		free(m);
		return 1;
	}
	else{
		return 0;
	}

}
 
/* Inorder walk RECURSIVE  not good for large trees!*/
void tree_inorder_walk(bnode* node, nb_show_fp show ){
	if(node){
		tree_inorder_walk(node->left, show);
		show(node->value, node->data);
		tree_inorder_walk(node->right, show);
	}
}

/* Destroy the tree form the root node */
void tree_destroy(bnode** node,  nb_binarytredicate_fp compare, nb_deallocator_fp dealloc){
	while(*node){
		tree_delete(node, (*node)->value, compare, dealloc);
	}
}
#endif
